package solution;


import solution.bean.ListNode;

import java.util.HashSet;
import java.util.Set;

/*
* 142
* */
public class DetectCycle {

    /*
    * 使用哈希表
    * 不符合题干需要的优化条件
    * */
    public ListNode solution1(ListNode head) {
//        ListNode pos = head;
//        Set<ListNode> visited = new HashSet<ListNode>();
//        while (pos != null){
//            if (visited.contains(pos)){
//                return pos;
//            }
//            else {
//                visited.add(pos);
//            }
//            pos = pos.next;
//        }
//        return null;

        //优化的写法
        Set<ListNode> set = new HashSet<>();
        while (head != null){
            if (!set.add(head)){
                return head;
            }
            head = head.next;
        }
        return null;
    }

    /*
    * 使用快慢指针
    * */
    public ListNode solution2(ListNode head){
        //不知道为什么会超时
//        if (head != null){
//            ListNode slow = head;
//            ListNode fast = head.next;
//            while (fast != slow){
//                if (fast == null && fast.next == null){
//                    return null;
//                }
//
//
//                slow = slow.next;
//                fast = fast.next.next;
//            }
//
//            ListNode ptr = head;
//            while (ptr != slow){
//                slow = slow.next;
//                ptr = ptr.next;
//            }
//            return ptr;
//        }
//
//        return null;

        //原始答案
//        if (head == null) {
//            return null;
//        }
//        ListNode slow = head, fast = head;
//        while (fast != null) {
//            slow = slow.next;
//            if (fast.next != null) {
//                fast = fast.next.next;
//            } else {
//                return null;
//            }
//            if (fast == slow) {
//                ListNode ptr = head;
//                while (ptr != slow) {
//                    ptr = ptr.next;
//                    slow = slow.next;
//                }
//                return ptr;
//            }
//        }
//        return null;

        //优化的写法
        if (head != null){
            ListNode fast = head;
            ListNode slow = head;
            while (fast != null){
                if (fast.next == null){
                    return null;
                }
                fast = fast.next.next;
                slow = slow.next;
                if (fast == slow){
                    ListNode ptr = head;
                    while (ptr != slow){
                        ptr = ptr.next;
                        slow = slow.next;
                    }

                    return ptr;
                }
            }
        }

        return null;
    }

    /*
    * 如果可以，在数据解构中添加一个属性用于标记
    * */


}
